/*************************************************************************
 * File Name:    Median_of_Two_Sorted_Arrays.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013/11/9 17:08:40
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Problem: Median of Two Sorted Arrays
 |
 | There are two sorted arrays A and B of size m and n respectively.
 | Find the median of the two sorted arrays.
 | The overall run time complexity should be O(log (m+n)).
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
private:
    int median_num3(int a, int b, int c)
    {
        int ma = max(max(a,b),c);
        int mi = min(min(a,b),c);
        return a + b + c - ma - mi;
    }

    // ensure m >= n
    int find_num(int A[], int m, int B[], int n, int p)
    {
        if (m == 0) return B[p - 1];

        if (n == 0) return A[p - 1];
        
        if (p == 1) return min(A[0], B[0]);
        
        if (n == 1) {
            if (m > 1) return median_num3(A[p - 1], A[p - 2], B[0]);
            return max(A[0], B[0]);
        }
        
        int pmid = min(n, p) / 2;

        if (A[pmid - 1] >= B[pmid - 1]) {
            if (m >= n - pmid) return find_num(A, m, B + pmid, n - pmid, p - pmid);
            return find_num(B + pmid, n - pmid, A, m, p - pmid);;
        } else {
            if (n >= m - pmid) return find_num(B, n, A + pmid, m - pmid, p - pmid);
            return find_num(A + pmid, m - pmid, B, n, p - pmid);
        }
    }

public:
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
        if (m >= n) {
            if ((m + n) & 1) return find_num(A, m, B, n, (m + n + 1) / 2);
            return (find_num(A, m, B, n, (m + n) / 2) + find_num(A, m, B, n, (m + n) / 2 + 1)) / 2.0;
        } else {
            if ((m + n) & 1) return find_num(B, n, A, m, (m + n + 1) / 2);
            return (find_num(B, n, A, m, (m + n) / 2) + find_num(B, n, A, m, (m + n) / 2 + 1)) / 2.0;
        }
    }
};

int
main(int argc, char *argv[])
{
    int A[] = {1};
    int B[] = {1};
    //int A[] = {100000};
    //int B[] = {100001};
    //int A[] = {1,1};
    //int B[] = {1,2};
    //int A[] = {1};
    //int B[] = {2,3,4,5,6,7};
    //int A[] = {459,1142,1513,1979,1994,2041,2383,2542,2711,2882,3299,3574,4029,4064,4221,4962,5834,6027,6053,6095,6207,7121,8226,8383,8525,8632,8719,8804,9374,9658,11113,11988,12543,12550,13238,13529,13550,13559,14419,14436,15018,15860,16046,16719,17985,18592,18710,18967,19509,19519,19804,20281,20289,20588,20821,20882,21583,22578,22744,22997,23280,23320,23334,23348,23688,23836,24697,25005,26124,26269,26517,26924,26928,27281,27858,28394,28958,29225,29489,29510,29804,29874,29949,30320,31020,31366,31408,31680,32055,32058,32397};
    //int B[] = {14,15,37,421,665,745,764,818,823,882,923,931,1189,1214,1607,1633,1832,1967,1999,2044,2052,2174,2334,2383,2433,2496,2508,2605,2678,2883,3062,3165,3260,3362,3371,3386,3392,3482,3487,3588,3724,3811,3884,3910,4232,4245,4292,4400,4422,4511,4731,4874,4887,4949,4988,5194,5217,5366,5395,5426,5516,5585,5595,5963,6004,6072,6083,6141,6248,6632,6812,6826,6829,6839,6860,6866,6991,6996,7082,7272,7285,7320,7334,7390,7405,7437,7603,7616,7810,7889,7926,7933,8035,8079,8094,8132,8139,8165,8292,8313,8375,8425,8438,8458,8541,8546,8574,8636,8639,8681,8712,8763,8775,8917,9246,9274,9283,9297,9322,9354,9372,9453,9810,9813,10157,10240,10341,10370,10385,10411,10448,10509,10588,10601,10633,10702,10707,10750,10780,10819,10945,11044,11064,11131,11252,11354,11400,11450,11559,11607,11675,11691,11907,11936,12022,12080,12162,12236,12238,12382,12502,12508,12650,12703,12741,12763,12769,12889,12915,12953,12974,13053,13138,13298,13355,13379,13460,13499,13554,13644,13742,13795,13829,13888,13922,14212,14419,14505,14527,14603,14696,14748,14929,14949,15145,15156,15231,15241,15320,15365,15488,15644,15820,15836,16055,16101,16126,16131,16166,16281,16283,16285,16493,16584,16587,16595,16618,16803,16804,16814,17129,17215,17236,17337,17434,17510,17544,17612,17631,17634,17720,17724,17875,17885,17895,18312,18397,18502,18586,18624,18674,18772,18920,18935,18978,19070,19080,19334,19370,19426,19494,19548,19713,19794,19914,19936,19984,20005,20028,20089,20095,20129,20160,20191,20206,20282,20395,20580,20827,20900,20937,20959,20998,20999,21003,21012,21014,21179,21193,21321,21432,21570,21606,21707,21778,21800,21812,21877,21936,21960,21962,22037,22058,22095,22120,22272,22457,22588,22602,22667,22767,22825,22836,23161,23165,23369,23373,23376,23437,23677,23916,23983,23986,24013,24031,24136,24212,24232,24340,24405,24442,24506,24527,24542,24612,24617,24821,24976,25178,25204,25206,25316,25336,25359,25501,25523,25526,25573,25594,25761,25780,25784,26012,26106,26236,26305,26358,26469,26476,26517,26660,26710,26796,26838,26970,27158,27405,27429,27441,27468,27487,27633,27749,27755,27790,27811,28028,28151,28222,28278,28293,28305,28358,28408,28471,28473,28493,28511,28515,28650,28682,28807,28814,28837,28907,28909,28997,29077,29136,29246,29263,29367,29455,29496,29566,29831,29997,30120,30161,30313,30419,30433,30501,30677,30821,30956,31067,31082,31122,31254,31327,31339,31495,31576,31694,31826,31831,32050,32084,32227,32405,32443,32501,32713};


    int m = sizeof(A) / sizeof(A[0]);
    int n = sizeof(B) / sizeof(B[0]);

    Solution sol;
    cout << sol.findMedianSortedArrays(A, m, B, n) << endl;

    return 0;
}
